/**
 * 真题描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
 * 使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
 */

let nums = [-1, 0, 1, 2, -1, -4] 
// 满足要求的三元组集合为 [ [-1, 0, 1], [-1, -1, 2] ]


/**
 * 双指针对撞法 
 *    先将目标数组排序
 *    遍历数组，固定当前遍历的位置，一个指针指向下一个位置，另一个指针指向最后一个位置
 *    指针每移动一个位置就 计算两个指针指向数字之和加上固定的那个数之后，是否等于0.
 *    因为已经对数组进行排序
 *      * 相加之和大于0，说明右侧的数偏大了，右侧指针左移
 *      * 相加之和小于0，则说明左侧的数偏小，左侧指针右移
 *    注意：
 *        需要重复元素跳过处理
 */
function threeNumbers (nums) {
  // 先对数组进行排序
  nums = nums.sort((a,b) => a-b)
  const length = nums.length
  const res = [] // 返回的数组
  // 因为另外有两个指针 所以只需要遍历到倒数第三个就ok
  for(let i = 0; i < length -2; i++) {
    let j = i + 1 // 左指针
    let k = length - 1 // 右指针
    // 判断重复的情况
    if(i>0 && nums[i]===nums[i-1]) {
      //跳过本次循环
      continue
    }
    while(j < k) { // 两个指针重合的时候停止
      if(nums[i] + nums[j] + nums[k] > 0) {
        k--
        // 处理元素重复的情况
        while(j<k && nums[k] === nums[k+1]) {
          // 右侧指针左移
          k--
        }
        
      } else if (nums[i] + nums[j] + nums[k] < 0) {
        j++
        // 处理元素重复的情况
        while(j< k && nums[j] === nums[j-1]) {
          // 左指针右移
          j++
        }
      } else {
        // 得到一组
        res.push([nums[i],nums[j],nums[k]])
        // 左右指针一起前进
        j++
        k--
        while(j<k && nums[j] === nums[j-1]) {
          // 左指针右移
          j++
        }
        while(j<k && nums[k] === nums[k+1]) {
          // 右侧指针左移
          k--
        }
      }
    }
    
  }
  return res
}

console.log(threeNumbers (nums))